package com.wfm.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class PFour0组合总和II{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
//    List<List<Integer>> res = new ArrayList<>();
//    List<Integer> path =new ArrayList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        visited = new boolean[candidates.length];
//        Arrays.sort(candidates);
//        dfs(candidates,0,target);
//        return res;
//    }
//    void dfs(int[] candidates,int start,int target){
//        if(target==0){
//            res.add(new ArrayList<>(path));
//            return;
//        }
//        for (int i = start; i < candidates.length; i++) {
//            if(candidates[i]>target) break;
//            if(i>start&&candidates[i]==candidates[i-1]) {
//                continue;
//            }
//            path.add(candidates[i]);
//            dfs(candidates,i+1,target-candidates[i]);
//            path.remove(path.size()-1);
//        }
//    }

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path =new ArrayList<>();
    boolean[] visited = null;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        visited = new boolean[candidates.length];
        Arrays.sort(candidates);
        dfs(candidates,0,target);
        return res;
    }
    void dfs(int[] candidates,int start,int target){
        if(target==0){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if(candidates[i]>target) break;
            if(i>0&&candidates[i]==candidates[i-1]&&visited[i-1]==false) {
                continue;
            }
            path.add(candidates[i]);
            visited[i]=true;
            dfs(candidates,i+1,target-candidates[i]);
            path.remove(path.size()-1);
            visited[i]=false;
        }
    }

    // 这种分开的好像写不出来
//    List<List<Integer>> res = new ArrayList<>();
//    List<Integer> path =new ArrayList<>();
//    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//        Arrays.sort(candidates);
//        for (int i = 0; i < candidates.length; i++) {
//            if(i>0&&candidates[i]==candidates[i-1]){
//                continue;
//            }
//            dfs(candidates,i,target);
//        }
//        return res;
//    }
//    void dfs(int[] candidates,int start,int target){
//        if(start>=candidates.length) return;
//        path.add(candidates[start]);
//        if(target-candidates[start]==0){
//            res.add(new ArrayList<>(path));
//        }
//        for (int j = start+1; j < candidates.length; j++) {
//            if(candidates[j]>target) break;
//            if(candidates[j]==candidates[j-1]) {
//                continue;
//            }
//            dfs(candidates,j+1,target-candidates[start]);
//        }
//        path.remove(path.size()-1);
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new PFour0组合总和II().new Solution();
//        List<List<Integer>> lists = solution.combinationSum2(new int[]{10, 1, 2, 7, 6, 1, 5},8);
//        System.out.println(lists);
        List<List<Integer>> lists = solution.combinationSum2(new int[]{10,1,2,7,6,1,5},8);
        System.out.println(lists);
    }
}